package leetcode.editor.cn.dsa03_stack;
//删除最外层的括号
public class RemoveOutermostParentheses1021_2 {
    public static void main(String[] args) {
        Solution solution = new RemoveOutermostParentheses1021_2().new Solution();
        String[] arr = {"(()())(())", "(()())(())(()(()))", "()()"};
        for (int i = 0; i < arr.length; i++) {
            String ret = solution.removeOuterParentheses(arr[i]);
            System.out.println(arr[i] + "====>" + ret);
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 自定义栈
    class Stack<E> {
        Object[] elements = new Object[5000];
        int index = -1; // 栈顶索引
        public Stack() {}
        // 往栈顶插入元素
        public void push(E c) {
            elements[++index] = c;
        }
        // 从栈顶获取数据，不移出
        public E peek() {
            if (index < 0) return null;
            return (E)elements[index];
        }
        public E pop() {
            E e = peek();
            if (e != null) {
                elements[index] = null; // 移出动作
                index--; // 栈顶下移
            }
            return e;
        }
        public boolean isEmpty() {
            return index == -1;
        }
    }
    class Solution {
        /**
         * 最优解：栈解法
         * 1.使用数组模拟一个栈，临时存储左括号字符
         *   push(Character) ; pop(); isEmpty()
         * 2.遍历字符串，根据情况进行入栈/出栈操作栈实现代码：
         *   读取到左括号，左括号入栈
         *   读取到右括号，左括号出栈
         * 3.判断栈是否为空，若为空，找到了一个完整的原语
         * 4.截取不含最外层括号的原语子串并进行拼接
         *
         * 边界问题：
         *     遍历字符串，注意索引越界：i < S.length()
         *     截取原语字符串时，注意起止索引：[start, end)
         * 细节问题：
         *     需要记录上一次截取原语子串之后的位置
         * @param str
         * @return
         */
        public String removeOuterParentheses(String str) {
            StringBuilder result = new StringBuilder();
            // 1.使用数组模拟一个栈，临时存储字符，替代计数器
            Stack stack = new Stack();
            int len = str.length();
            int lastOpr = 0;

            // 2.遍历字符串，根据情况进行入栈 / 出栈操作
            for (int i = 0; i < len; i++) {
                char c = str.charAt(i);
                if (c == '(') { // 遇到左括号，左括号入栈
                    stack.push(c);
                } else { // 遇到右括号，左括号出栈
                    stack.pop();
                }
                // 3.判断栈是否为空，若为空，找到了一个完整的原语
                if (stack.isEmpty()) {
                    // 4.截取不含最外层括号的原语子串并进行拼接
                    result.append(str.substring(lastOpr+1, i));
                    lastOpr = i + 1;
                }
            }
            return result.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
